/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2021年12月12日
*   描    述：
*   Copyright (C) 2021 All rights reserved.
*
* ================================================================*/

#include <iostream>

using namespace std;

class Solution
{
public:
    int integerReplacement(int n)
    {
        int ans = 0;
        while (n != 1)
        {
            if (n % 2 == 0)
            {
                ans++;
                n >>= 1;
            }
            else if (n % 4 == 3)
            {
                if (n == 3)
                {
                    return ans + 2;
                }
                ans += 2;
                n = ((n >> 1) + 1);
            }
            else
            {
                ans += 2;
                n >>= 1;
            }
        }

        return ans;
    }
};

class Solution
{
public:
    int integerReplacement(int n)
    {
        int ans = 0;
        while (n != 1)
        {
            if (n % 2 == 0)
            {
                ans++;
                n >>= 1;
            }
            else if (n % 4 == 3)
            {
                if (n == 3)
                {
                    return ans + 2;
                }
                ans += 2;
                n = ((n - 1) / 2 + 1);
            }
            else
            {
                ans += 2;
                n = (n - 1) / 2;
            }
        }

        return ans;
    }
};
